package com.shixianchen.review_the_day_before.day5;

import com.shixianjun.sort.Sortable;
import com.shixianjun.sort.SortableElement;

/**
 * @author ShiXianChen
 * @version V1.0.0
 * @Description TODO
 * @date 2022/11/8 21:08
 */
public class insertSort implements Sortable {
    @Override
    public void sort(SortableElement[] arr) {
        //默认第一个为有序的数据
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            //获取要插入的数据
            SortableElement insertIndex = arr[i];
            //得到最后的一个有序数据
            int j = i-1;

            //从后往前遍历数据
            for (; j >= 0 && arr[j].value >insertIndex.value; j--){
                arr[j+1] = arr[j];
            }

            //放入数据
            arr[j+1] = insertIndex;
        }
    }
}
